#include<stdio.h>
#define MAX_NUM 100


#define LChild(i)  (2*(i)+1)
#define RChild(i)  (2*(i)+2)

int Parent(int i)
{
	return (int) ((i)-1)/2;
}
void swap(int *x,int *y)
{
    int temp = *x;
    *x= *y;
    *y = temp;
    return;
}
typedef struct Heap
{
    int data[MAX_NUM];
    int num; //堆中数据实际大小
}Heap;
/*
    上滤
    index 需要上滤节点的秩
*/
void percolateUp(Heap * heap,int index)//上滤
{
    while (index>0)
    {
        if ((heap->data)[index] > (heap->data)[Parent(index)])
        {
            swap(&heap->data[index],&heap->data[Parent(index)]);
            index = Parent(index);
        }
        else
            break;
    }
}
/*
    下滤
    index 需要下滤节点的秩
*/

void percolateDown(Heap * heap,int index)//下滤
{
    int index2 ;
    while (index <heap->num)
    {
        //printf("heap value %d\n",heap->data[index]);
        if (LChild(index)<heap->num)
        {
            if (RChild(index)<heap->num)
            {
                index2 = heap->data[LChild(index)]>=heap->data[RChild(index)]?LChild(index):RChild(index);
            }
            else
            {
                index2 = LChild(index);
            }

        }
        else
        {
            break;
        }

        if(heap->data[index] <heap->data[index2])
        {
            swap(&heap->data[index] ,&heap->data[index2]);
            index  = index2;
        }
        else
        {
            break;
        }

    }
}
void Heap_insert(Heap * heap, int x)
{
    if(heap->num<MAX_NUM)
    {
        heap->data[heap->num] =x;
        heap->num ++;
        percolateUp(heap,heap->num-1);//上滤
    }

}

int Heap_delMax(Heap * heap, int x)
{
    int max_elem = heap->data[0];
    if(heap->num ==1)
    {
        heap->num --;
        return max_elem;
    }

    swap(&heap->data[0],&heap->data[heap->num-1]);
    heap->num--;
    percolateDown(heap,0);//下滤
    return max_elem;
}
void Heapify(Heap * heap)
{
	int i;
    for (i =heap->num-1;i>=0;i--)
    {
        percolateDown(heap,i);
    }
}
void Heap_disp(Heap * heap)
{
	int i;
    for (i=0;i<heap->num;i++)
    {
        printf("%d ",heap->data[i]);

    }
    printf("\n");
}

void Heap_init(Heap * heap)
{
    heap->num =0;
}
int main()
{
    Heap  heap ;
    Heap_init( & heap);
    int a =0;
    /*while (1)

    {
        printf("请输入一个数字：");
        scanf("%d",&a);
        if(a=-1000)
        {
            break;
        }
        Heap_insert(&heap,a);
        Heap_disp(&heap);

    }*/

    heap.data[0] = 2;
    heap.data[1] = 1;
    heap.data[2] = 5;
    heap.num =3;
    Heapify(&heap);
    Heap_disp(&heap);

    Heap_insert(&heap,6);

    Heap_disp(&heap);
    Heap_insert(&heap,7);

    Heap_disp(&heap);


    return 0;

}